//
// Created by shenbin on 2022/5/7.
//

#ifndef ALGORITHM_TRAINNING_C04_LC77_H
#define ALGORITHM_TRAINNING_C04_LC77_H

#include <vector>

using namespace std;

class LeetCode77 {
public:
    vector<vector<int>> combine(int n, int k) {
        this->n = n;
        this->k = k;
        recur(1);
        return ans;

    }

private:
    vector<int> chosen;
    vector<vector<int>> ans;
    int n, k;

    void recur(int i) {
        // 剪枝：如果已经选了超过k个，或者选剩下全部也不够k个，说明不合法了，提前退出
        if (chosen.size() > k || chosen.size() + (n - i + 1) < k)return;
        // 递归边界
        if (i == n + 1) {
            ans.push_back(chosen);
            return;
        }
        // 每层的相似逻辑，1选或不选
        recur(i + 1);
        chosen.push_back(i);
        recur(i + 1);
        // 还原现场
        chosen.pop_back();
    }
};

#endif //ALGORITHM_TRAINNING_C04_LC77_H
